1083. Последовательность

В числовой последовательности a₁, a₂, a₃, ... известен первый член, а каждый следующий вычисляется по следующей формуле:

a_i = (a_i-1 * a_i-1) mod 10000

Найдите n-ый член этой последовательности.

Вход. В первой строке заданы два целых числа a₁ и n (0 ≤ a₁ ≤ 10000, 1 ≤ n ≤ 2000000010).

Выход. Выведите одно целое число a_n.

Пример входа	Пример выхода
4 3	256

РЕШЕНИЕ

возведение в степень

Анализ алгоритма

Выразим первые члены последовательности через a₁:

· a₂ = a₁² mod 10000,

· a₃ = a₂² mod 10000 = a₁⁴ mod 10000,

· a₄ = a₃² mod 10000 = a₂⁴ mod 10000 = a₁⁸ mod 10000

Таким образом, формулу можно записать в виде:

a_i = a_i-1² mod 10000

Откуда следует, что для вычисления a_n достаточно возвести a₁ в степень 2^n–1 по модулю 10000:

Учитывая, что

a^b mod n = a^{b mod j(n)} mod n,

для получения результата res следует выполнить следующие вычисления:

· Вычислить значение x = 2^n–1 mod j(10000) = 2^n–1 mod 4000,

· Затем вычислить res = a₁^x mod 10000

Реализация алгоритма

Функция PowMod вычисляет значение xⁿ mod m.

int PowMod(int x, int n, int m)

{

if (n == 0) return 1;

if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

return (x * PowMod(x, n - 1, m)) % m;

}

Читаем входные данные.

scanf("%d %d",&a,&n);

Вычисляем x = 2^n–1 mod 4000. После чего находим и выводим ответ:

res = a^x mod 10000

x = PowMod(2,n-1,4000);

res = PowMod(a,x,10000);

printf("%d\n",res);

Java реализация

import java.util.*;

public class Main

{

static long PowMod(long x, long n, long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

return (x * PowMod(x, n - 1, m)) % m;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long a = con.nextLong();

long n = con.nextLong();

long x = PowMod(2,n-1,4000);

long res = PowMod(a,x,10000);

System.out.println(res);

con.close();

}

}